﻿/*链表，头结点不存储数据*/
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

//#pragma execution_character_set("utf-8")

#include <stddef.h>

typedef int ElemType;

typedef struct Node{
    ElemType data;
    struct Node *next;
    Node *random;
    Node():data(-1),next(NULL),random(NULL){}
}LinkNode,ListNode,*LinkList;

typedef int Status;

/*链表其他问题*/
/*链表其他问题测试函数*/
void LinkedListOtherQuestionTest();
/*1 输出链表中倒数第k个结点*/
void Q1_findTest();
int Q1_find(LinkList L,const int k);
/*2 反转链表，输出链表所有元素*/
void Q2_reverseTest();
LinkList Q2_reverse(LinkList L);
/*3 输入两个单调递增的链表，输出两个链表合成后的链表，
 * 当然我们需要合成后的链表满足单调不减规则。*/
void Q3MergeTest();
ListNode* Q3Merge(ListNode* pHead1, ListNode* pHead2);
/*4 复杂链表的复制(头结点保存数据)
*输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，
* 另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。
* （注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
* 思路：
* 1 创建新的为每个结点创建一个克隆结点放到原结点的后面。new A1(A);A->next=A1;
* 2 遍历链表。克隆结点的random指针原结点random指针所指向元素的next结点，A1->random=A->random->next;
* 3  遍历链表，拆分两个链表。
 */
void Q4_CloneTest();//不完整测试
ListNode* Q4_Clone(ListNode*pHead);




/*链表基本问题*/
//测试函数
void LinkedBaseListTest();

//创建有序链表
LinkList CreatSortedLinkList(LinkList L,int n);
LinkList CreatSortedLinkList_NoHead(const int n);
//头插法,创建n个元素
void CreateHead(LinkList L,int n);
//尾插法
void CreateTail(LinkList L,int n);
//访问每个节点
void Visit(ElemType e);
//初始化头结点
Status InitList(LinkList *L);
//是否为空
Status IsEmpty(LinkList L);
//获取长度
int Length(LinkList L);
//获取第i个元素的数据，e返回
bool GetElem(LinkList L,int i,ElemType *e);
//返回第一个与e值相同的节点的位置
int LocateElem(LinkList L,ElemType e);
//在第i个位置插入新数据
bool Insert(LinkList L,int i,ElemType e);
//删除第i个元素，用e返回其值
bool Delete(LinkList L,int i,ElemType *e);
//依次输出链表每个元素
int Display(LinkList L);
int Display_NoHead(LinkList L);

//销毁
int Destroty(LinkList *L);



#endif // LINKEDLIST_H
